<div class="problemindexholder" problemindex="B">
 <div class="ttypography">
  <div class="problem-statement">
   <div class="header">
    <div class="title">
     B. Interactive LowerBound
    </div>
    <div class="time-limit">
     <div class="property-title">
      time limit per test
     </div>
     1 second
    </div>
    <div class="memory-limit">
     <div class="property-title">
      memory limit per test
     </div>
     256 megabytes
    </div>
    <div class="input-file">
     <div class="property-title">
      input
     </div>
     standard input
    </div>
    <div class="output-file">
     <div class="property-title">
      output
     </div>
     standard output
    </div>
   </div>
   <div>
    <p>
     <span class="tex-font-style-it">
      This is an interactive problem.
     </span>
    </p>
    <p>
     You are given a
     <span class="tex-font-style-bf">
      sorted
     </span>
     in increasing order singly linked list. You should find the minimum integer in the list which is greater than or equal to
     <span class="tex-span">
      <i>
       x
      </i>
     </span>
     .
    </p>
    <p>
     More formally, there is a singly liked list built on an array of
     <span class="tex-span">
      <i>
       n
      </i>
     </span>
     elements. Element with index
     <span class="tex-span">
      <i>
       i
      </i>
     </span>
     contains two integers:
     <span class="tex-span">
      <i>
       value
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
     </span>
     is the integer value in this element, and
     <span class="tex-span">
      <i>
       next
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
     </span>
     that is the index of the next element of the singly linked list (or
     <span class="tex-font-style-tt">
      -1
     </span>
     , if the current element is the last). The list is sorted, i.e. if
     <span class="tex-span">
      <i>
       next
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
      ≠  - 1
     </span>
     , then
     <span class="tex-span">
      <i>
       value
      </i>
      <sub class="lower-index">
       <i>
        next
       </i>
       <sub class="lower-index">
        <i>
         i
        </i>
       </sub>
      </sub>
      &gt;
      <i>
       value
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
     </span>
     .
    </p>
    <p>
     You are given the number of elements in the list
     <span class="tex-span">
      <i>
       n
      </i>
     </span>
     , the index of the first element
     <span class="tex-span">
      <i>
       start
      </i>
     </span>
     , and the integer
     <span class="tex-span">
      <i>
       x
      </i>
     </span>
     .
    </p>
    <p>
     You can make up to
     <span class="tex-span">
      2000
     </span>
     queries of the following two types:
    </p>
    <ul>
     <li>
      <span class="tex-font-style-tt">
       ? i
      </span>
      (
      <span class="tex-span">
       1 ≤
       <i>
        i
       </i>
       ≤
       <i>
        n
       </i>
      </span>
      ) — ask the values
      <span class="tex-span">
       <i>
        value
       </i>
       <sub class="lower-index">
        <i>
         i
        </i>
       </sub>
      </span>
      and
      <span class="tex-span">
       <i>
        next
       </i>
       <sub class="lower-index">
        <i>
         i
        </i>
       </sub>
      </span>
      ,
     </li>
     <li>
      <span class="tex-font-style-tt">
       ! ans
      </span>
      — give the answer for the problem: the minimum integer, greater than or equal to
      <span class="tex-span">
       <i>
        x
       </i>
      </span>
      , or
      <span class="tex-font-style-tt">
       ! -1
      </span>
      , if there are no such integers. Your program should terminate after this query.
     </li>
    </ul>
    <p>
     Write a program that solves this problem.
    </p>
   </div>
   <div class="input-specification">
    <div class="section-title">
     Input
    </div>
    <p>
     The first line contains three integers
     <span class="tex-span">
      <i>
       n
      </i>
     </span>
     ,
     <span class="tex-span">
      <i>
       start
      </i>
     </span>
     ,
     <span class="tex-span">
      <i>
       x
      </i>
     </span>
     (
     <span class="tex-span">
      1 ≤
      <i>
       n
      </i>
      ≤ 50000
     </span>
     ,
     <span class="tex-span">
      1 ≤
      <i>
       start
      </i>
      ≤
      <i>
       n
      </i>
     </span>
     ,
     <span class="tex-span">
      0 ≤
      <i>
       x
      </i>
      ≤ 10
      <sup class="upper-index">
       9
      </sup>
     </span>
     ) — the number of elements in the list, the index of the first element and the integer
     <span class="tex-span">
      <i>
       x
      </i>
     </span>
     .
    </p>
   </div>
   <div class="output-specification">
    <div class="section-title">
     Output
    </div>
    <p>
     To print the answer for the problem, print
     <span class="tex-font-style-tt">
      ! ans
     </span>
     , where
     <span class="tex-font-style-tt">
      ans
     </span>
     is the minimum integer in the list greater than or equal to
     <span class="tex-span">
      <i>
       x
      </i>
     </span>
     , or
     <span class="tex-font-style-tt">
      -1
     </span>
     , if there is no such integer.
    </p>
   </div>
   <div>
    <div class="section-title">
     Interaction
    </div>
    <p>
     To make a query of the first type, print
     <span class="tex-font-style-tt">
      ? i
     </span>
     (
     <span class="tex-span">
      1 ≤
      <i>
       i
      </i>
      ≤
      <i>
       n
      </i>
     </span>
     ), where
     <span class="tex-font-style-tt">
      i
     </span>
     is the index of element you want to know information about.
    </p>
    <p>
     After each query of type
     <span class="tex-font-style-tt">
      ?
     </span>
     read two integers
     <span class="tex-span">
      <i>
       value
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
     </span>
     and
     <span class="tex-span">
      <i>
       next
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
     </span>
     (
     <span class="tex-span">
      0 ≤
      <i>
       value
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
      ≤ 10
      <sup class="upper-index">
       9
      </sup>
     </span>
     ,
     <span class="tex-span">
      - 1 ≤
      <i>
       next
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
      ≤
      <i>
       n
      </i>
     </span>
     ,
     <span class="tex-span">
      <i>
       next
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
      ≠ 0
     </span>
     ).
    </p>
    <p>
     It is guaranteed that if
     <span class="tex-span">
      <i>
       next
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
      ≠  - 1
     </span>
     , then
     <span class="tex-span">
      <i>
       value
      </i>
      <sub class="lower-index">
       <i>
        next
       </i>
       <sub class="lower-index">
        <i>
         i
        </i>
       </sub>
      </sub>
      &gt;
      <i>
       value
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
     </span>
     , and that the array values give a valid singly linked list with
     <span class="tex-span">
      <i>
       start
      </i>
     </span>
     being the first element.
    </p>
    <p>
     Note that you can't ask more than
     <span class="tex-span">
      1999
     </span>
     queries of the type
     <span class="tex-font-style-tt">
      ?
     </span>
     .
    </p>
    <p>
     If
     <span class="tex-span">
      <i>
       next
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
      =  - 1
     </span>
     and
     <span class="tex-span">
      <i>
       value
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
      =  - 1
     </span>
     , then it means that you asked more queries than allowed, or asked an invalid query. Your program should immediately terminate (for example, by calling
     <span class="tex-font-style-tt">
      exit(0)
     </span>
     ). You will receive "
     <span class="tex-font-style-tt">
      Wrong Answer
     </span>
     ", it means that you asked more queries than allowed, or asked an invalid query. If you ignore this, you can get other verdicts since your program will continue to read from a closed stream.
    </p>
    <p>
     Your solution will get "Idleness Limit Exceeded", if you don't print anything or forget to
     <span class="tex-font-style-tt">
      flush
     </span>
     the output, including the final answer.
    </p>
    <p>
     To
     <span class="tex-font-style-tt">
      flush
     </span>
     you can use (just after printing a query and line end):
    </p>
    <ul>
     <li>
      <span class="tex-font-style-tt">
       fflush(stdout)
      </span>
      in C++;
     </li>
     <li>
      <span class="tex-font-style-tt">
       System.out.flush()
      </span>
      in Java;
     </li>
     <li>
      <span class="tex-font-style-tt">
       stdout.flush()
      </span>
      in Python;
     </li>
     <li>
      <span class="tex-font-style-tt">
       flush(output)
      </span>
      in Pascal;
     </li>
     <li>
      For other languages see documentation.
     </li>
    </ul>
    <p>
     <span>
      <span class="tex-font-style-bf">
       Hacks format
      </span>
     </span>
    </p>
    <p>
     For hacks, use the following format:
    </p>
    <p>
     In the first line print three integers
     <span class="tex-span">
      <i>
       n
      </i>
     </span>
     ,
     <span class="tex-span">
      <i>
       start
      </i>
     </span>
     ,
     <span class="tex-span">
      <i>
       x
      </i>
     </span>
     (
     <span class="tex-span">
      1 ≤
      <i>
       n
      </i>
      ≤ 50000
     </span>
     ,
     <span class="tex-span">
      1 ≤
      <i>
       start
      </i>
      ≤
      <i>
       n
      </i>
     </span>
     ,
     <span class="tex-span">
      0 ≤
      <i>
       x
      </i>
      ≤ 10
      <sup class="upper-index">
       9
      </sup>
     </span>
     ).
    </p>
    <p>
     In the next
     <span class="tex-span">
      <i>
       n
      </i>
     </span>
     lines print the description of the elements of the list: in the
     <span class="tex-span">
      <i>
       i
      </i>
     </span>
     -th line print two integers
     <span class="tex-span">
      <i>
       value
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
     </span>
     and
     <span class="tex-span">
      <i>
       next
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
     </span>
     (
     <span class="tex-span">
      0 ≤
      <i>
       value
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
      ≤ 10
      <sup class="upper-index">
       9
      </sup>
     </span>
     ,
     <span class="tex-span">
      - 1 ≤
      <i>
       next
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
      ≤
      <i>
       n
      </i>
     </span>
     ,
     <span class="tex-span">
      <i>
       next
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
      ≠ 0
     </span>
     ).
    </p>
    <p>
     The printed structure should be a valid singly linked list. In particular, it should be possible to reach all elements from
     <span class="tex-span">
      <i>
       start
      </i>
     </span>
     by following links
     <span class="tex-span">
      <i>
       next
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
     </span>
     , and the last element
     <span class="tex-span">
      <i>
       end
      </i>
     </span>
     should have
     <span class="tex-font-style-tt">
      -1
     </span>
     in the
     <span class="tex-span">
      <i>
       next
      </i>
      <sub class="lower-index">
       <i>
        end
       </i>
      </sub>
     </span>
     .
    </p>
   </div>
   <div class="sample-tests">
    <div class="section-title">
     Example
    </div>
    <div class="sample-test">
     <div class="input">
      <div class="title">
       Input
      </div>
      <pre>5 3 80<br/>97 -1<br/>58 5<br/>16 2<br/>81 1<br/>79 4<br/></pre>
     </div>
     <div class="output">
      <div class="title">
       Output
      </div>
      <pre>? 1<br/>? 2<br/>? 3<br/>? 4<br/>? 5<br/>! 81</pre>
     </div>
    </div>
   </div>
   <div class="note">
    <div class="section-title">
     Note
    </div>
    <p>
     You can read more about singly linked list by the following link:
     <a href="https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list">
      https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list
     </a>
    </p>
    <center>
     <p>
      The illustration for the first sample case. Start and finish elements are marked dark.
      <img class="tex-graphics" src="/predownloaded/5d/98/5d98b51b4d1724f766ee5573ffa6d86145121f30.png" style="max-width: 100.0%;max-height: 100.0%;"/>
     </p>
    </center>
   </div>
  </div>
  <p>
  </p>
 </div>
</div>
